二叉搜索树的后序遍历序列(Java) |
您所在的位置:网站首页 › 序列1-9构成的二叉搜索树的层序遍历前六位 中文数字 › 二叉搜索树的后序遍历序列(Java) |
题目: 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true。否则返回false。假设输入的数组的任意两个数字都互不相同。 思路: 满二叉树:从高到低,除了叶结点外,所有结点的左右结点都存在。 完全二叉树:比满二叉树少几个叶结点,从左向右放子结点。 平衡二叉树:空树或者它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树也都是平衡树。、
二叉搜索树:空树或者二叉树的所有结点比它的左子结点大,比它的右子结点小。
例如输入数组{5, 7, 6, 9, 11, 10, 8},则返回true,因为这个整数序列是上图二叉搜索树的后序遍历结果。如果输入的数组是{7, 4, 6, 5},由于没有哪颗二叉搜索树的后序遍历的结果是这个序列,因此返回false。 在后序遍历得到的序列中,最后一个数字是树的根结点的值。数组中前面的数字可以分为两部分:第一部分是左子树结点的值,它们都比根结点的值小;第二部分是右子树结点的值,它们都比根结点的值大。 以数组{5, 7, 6, 9, 11, 10, 8}为例,后序遍历的结果中最后一个值8就是根结点,在这个数组中前3个数字5,7, 6都比8 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |